package 数据结构.排序.实例;
/**
 *
 * */
import java.util.Arrays;
import java.util.Scanner;

public class $08_堆排序 {

//大根堆的创建过程可以采用从数组的一般位置开始下沉的方式进行

   static void chuangjianshu(int[] a,int sum){//大根堆的创建
        int []b=new int[sum+1];
        int i=1;int j;
        while (i<=sum){//创建的数据，从第一个开始进行创建
            b[i]=a[i];
            j=i;
            while (j>1){//调整数据，使得每一个数据的插入后都能够保证为大根堆
                if(b[j]>b[j/2]){
                 int t=b[j];b[j]=b[j/2];b[j/2]=t;
                 j=j/2;
                }
                else
                    j=0;
            }
            i++;
        }
        for (int m=1;m<=sum;m++)
            a[m]=b[m];
   }
    public static void min(int[] a,int sum){
       //堆顶元素和目前的最后一个原素进行交换；实现的结果也就是目前的最大数（即堆顶）换到目前剩下的数组的末尾
       int x=a[1];a[1]=a[sum];a[sum]=x;
       chuangjianshu(a,sum-1);//对剩下的数据进行大根堆创建
    }
    public static void main(String[] args) {

        Scanner input=new Scanner(System.in);
        System.out.println("请输入数组的数据长度");
        int sum=input.nextInt();int sum1=sum;
        int x=1;
        int []a=new int[sum+1];
        while(x<=sum){
            System.out.println("请输入第"+x+"个数据:");
            a[x]=input.nextInt();
            x++;
        }
        chuangjianshu(a,sum);
        while(sum>0){//多次的大根堆进行排序
            min(a,sum);
            sum--;
        }
        for (int m=1;m<=sum1;m++)
            a[m-1]=a[m];
            a[sum1]=0;
        System.out.println(Arrays.toString(a));
    }
}
